package com.linyaonan.leetcode.medium._930;

import java.util.HashMap;

/**
 * 给你一个二元数组 nums ，和一个整数 goal ，请你统计并返回有多少个和为 goal 的 非空 子数组。
 * <p>
 * 子数组 是数组的一段连续部分。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [1,0,1,0,1], goal = 2
 * 输出：4
 * 解释：
 * 有 4 个满足题目要求的子数组：[1,0,1]、[1,0,1,0]、[0,1,0,1]、[1,0,1]
 * 示例 2：
 * <p>
 * 输入：nums = [0,0,0,0,0], goal = 0
 * 输出：15
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= nums.length <= 3 * 10^4
 * nums[i] 不是 0 就是 1
 * 0 <= goal <= nums.length
 *
 * @author: Lin
 * @date: 2024/11/15
 */
public class BinarySubarraysWithSum {

    /**
     * 前缀和思路：nums = [1,0,1,0,1], goal = 2
     * sum=[1,1,2,2,3]
     *
     * @param nums
     * @param goal
     * @return
     */
    public int numSubarraysWithSum(int[] nums, int goal) {
        int result = 0;
        HashMap<Integer, Integer> saved = new HashMap<>();
        int add = 0;
        for (int i = 0; i < nums.length; i++) {
            saved.put(add, saved.getOrDefault(add, 0) + 1);
            add += nums[i];
            result += saved.getOrDefault(add - goal, 0);
        }

        return result;
    }

}
